#include <vector>
#include <math.h>

using namespace std;


/**
 * @brief 718. 最长重复子数组
 * https://leetcode.cn/problems/maximum-length-of-repeated-subarray/
 */
class Solution {
public:
    int findLength(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size();
        int n = nums2.size();
        vector<vector<int>> dp(m+1, vector<int>(n+1, 0));

        int maxAll = 0;
        for (int i=0; i<m; i++) {
            for (int j=0; j<n; j++) {
                if (nums1[i] == nums2[j]) {
                    dp[i+1][j+1] = 1 + dp[i][j];  // stores longest common prefix of nums1[i] and nums2[j]
                } else {
                    dp[i+1][j+1] = 0;  // common prefix length is 0
                }
                maxAll = max(maxAll, dp[i+1][j+1]);
            }
        }

        return maxAll;
    }
};
